package com.cd.algorithm.order.code;

import java.util.*;

/**
 * 拓扑排序
 * 思路：
 * 1. 首先，创建一个图的邻接表表示，并记录每个顶点的入度。
 * 2. 然后，将所有入度为0的顶点放入队列。
 * 3. 只要队列不为空，就不断进行BFS，每次从队列中取出一个顶点，将其添加到结果列表中，并遍历其邻居，将它们的入度减1，并将入度减为0的顶点加入队列。
 * 4. 检查是否所有顶点都已经在结果列表中，如果不是，说明图中存在环，无法进行拓扑排序。
 * 时间复杂度：O(V+E)，其中V是顶点数，E是边数。
 * 空间复杂度：O(V)，其中V是顶点数。
 */
public class TopologicalSort {
    public static void main(String[] args) {
        TopologicalSort topo = new TopologicalSort(6);
        topo.addEdge(5, 2);
        topo.addEdge(5, 0);
        topo.addEdge(4, 0);
        topo.addEdge(4, 1);
        topo.addEdge(2, 3);
        topo.addEdge(3, 1);

        List<Integer> order = topo.topologicalSort();
        System.out.println("Topological Order: " + order);
    }
    private List<List<Integer>> graph; // 图的邻接表表示
    private int[] indegree; // 记录每个顶点的入度

    public TopologicalSort(int vertices) {
        graph = new ArrayList<>(Collections.nCopies(vertices, new ArrayList<>()));
        indegree = new int[vertices];
    }

    // 添加有向边
    public void addEdge(int source, int destination) {
        graph.get(source).add(destination);
        indegree[destination]++;
    }

    // 拓扑排序
    public List<Integer> topologicalSort() {
        List<Integer> result = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();

        // 将所有入度为0的顶点放入队列
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.add(i);
            }
        }

        // 只要队列不为空，就不断进行BFS
        while (!queue.isEmpty()) {
            int current = queue.poll();

            // 将当前顶点添加到结果列表中
            result.add(current);

            // 遍历当前顶点的所有邻居，降低它们的入度，并将入度降为0的顶点加入队列
            for (int neighbor : graph.get(current)) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    queue.add(neighbor);
                }
            }
        }

        // 检查是否所有顶点都已经在结果列表中
        if (result.size() != graph.size()) {
            throw new IllegalArgumentException("The given graph contains cycles and cannot be topologically sorted.");
        }

        return result;
    }
}
